/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package model.kruskal;

import java.util.Collections;
import java.util.LinkedList;
import model.Clustering;
import model.DistanceCalculation;
import model.InitRandomPoints;
import model.Point;

/**
 *
 * @author Stupi
 */
public class Kruskal implements Clustering {

    LinkedList<KruskalObject> allPossibleConnections;
    LinkedList<KruskalObject> madeConnections;
    private Point[] points;
    private LinkedList<Point>[] clusters;
    private int[] id;    // id[i] = parent of i
    private int[] sz;    // sz[i] = number of objects in subtree rooted at i
    private int count;   // number of components
    private int numberOfClusters;

    public Kruskal(int numOfClusters, int numOfPoints) {
        allPossibleConnections = new LinkedList<>();
        madeConnections = new LinkedList<>();
        points = InitRandomPoints.getPoints();
        clusters = new LinkedList[numOfClusters];
        count = numOfPoints;
        numberOfClusters = numOfClusters;
        id = new int[numOfPoints];
        sz = new int[numOfPoints];
        for (int i = 0; i < numOfPoints; i++) {
            id[i] = i;
            sz[i] = 1;
        }
      
    }

    @Override
    public void cluster() {
      
        makePointPairs();
        connectPoints(numberOfClusters, points, allPossibleConnections);
        fillClustersArray(numberOfClusters);
       

//        arangeClusters();
    }

    @Override
    public LinkedList<Point>[] getClusters() {
        return clusters;
    }

    /**
     * Returns the number of components.
     *
     * @return the number of components (between 1 and N)
     */
    public int count() {
        return count;
    }

    /**
     * Returns the component identifier for the component containing site
     * <tt>p</tt>.
     *
     * @param p the integer representing one site
     * @return the component identifier for the component containing site
     * <tt>p</tt>
     * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
     */
    public int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    /**
     * Are the two sites <tt>p</tt> and <tt>q</tt> in the same component?
     *
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @return <tt>true</tt> if the two sites <tt>p</tt> and <tt>q</tt>
     * are in the same component, and <tt>false</tt> otherwise
     * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0
     * <= q < N
     */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * Merges the component containing site<tt>p</tt> with the component
     * containing site <tt>q</tt>.
     *
     * @param p the integer representing one site
     * @param q the integer representing the other site
     * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0
     * <= q < N
     */
    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j) {
            return;
        }

        // make smaller root point to larger one
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
        count--;
    }

    public void makePointPairs() {

        for (int i = 0; i < points.length - 1; i++) {

            for (int j = i + 1; j < points.length; j++) {

                KruskalObject ko = new KruskalObject();
                ko.setPoint1(points[i]);

                ko.setPoint2(points[j]);

                ko.setDistanceBetweenPoints(DistanceCalculation.calculateDistance(points[i], points[j]));
                allPossibleConnections.add(ko);
            }
        }
        Collections.sort(allPossibleConnections);
      

    }

    /**
     * Reads in a sequence of pairs of point IDs from list of KruskalObject,
     * where each list item represents possible connection between two points ;
     *
     * @param numberOfClusters
     * @param points LinkedList<KruskalObject> contains all possible connections
     * between points
     * @param list
     */
    public void connectPoints(int numberOfClusters, Point[] points, LinkedList<KruskalObject> list) {

        int connectionsMadeCounter = 0;
        for (int i = 0; i < allPossibleConnections.size(); i++) {
           
            if (connectionsMadeCounter < (points.length - numberOfClusters)) {

                int firstPoint = list.get(i).getPoint1().getSequenceNumber();
                int secondPoint = list.get(i).getPoint2().getSequenceNumber();
                if (connected(firstPoint, secondPoint)) {
                    continue;
                }
                union(firstPoint, secondPoint);
                connectionsMadeCounter++;
               
            } else {
                break;
            }
        }
            System.out.println(connectionsMadeCounter);

    }

    public void fillClustersArray(int numOfClusters) {
        for (int i = 0; i < points.length; i++) {
            int root = find(points[i].getSequenceNumber());//nadji redni broj korena
            Point currentpoint = points[i];
            Point rootPoint = null;
            for (Point point : points) {
                if (point.getSequenceNumber() == root) {
                    rootPoint = point;// preko rednog broja korena nadji koren-tacku
                    break;
                }
            }
            for (int j = 0; j < clusters.length; j++) {
                if (clusters[j] == null) {
                    clusters[j] = new LinkedList<>();
                    clusters[j].add(rootPoint);// prvo inicajalizuj, pa ubaci koren na pocetak liste jednog klastera
                }
                //ako je koren tacke jednak korenu klastera
                if (clusters[j].get(0).getSequenceNumber() == root) {
                    //i ako je tacka razlicita od koren-tacke dodaj tacku u listu tog klastera
                    if (clusters[j].get(0).getSequenceNumber() != currentpoint.getSequenceNumber()) {
                        clusters[j].add(currentpoint);
                    }
                    break;
                }
            }
        }
      
    }

}
